Search for: All records

Nonconvex quadratically constrained programs (QCPs) are generally NP-hard and challenging problems. In this paper, we propose two novel mixed-integer linear programming (MILP) approximations for a nonconvex QCP. Our method begins by utilizing an eigenvalue-based decomposition to express the nonconvex quadratic function as the difference of two convex functions. We then introduce an additional variable to partition each nonconvex constraint into a second-order cone (SOC) constraint and the complement of an SOC constraint. We employ two polyhedral approximation approaches to approximate the SOC constraint. The complement of an SOC constraint is approximated using a combination of linear and complementarity constraints. As a result, we approximate the nonconvex QCP with two linear programs with complementarity constraints (LPCCs). More importantly, we prove that the optimal values of the LPCCs asymptotically converge to that of the original nonconvex QCP. By proving the boundedness of the LPCCs, we further reformulate the LPCCs as MILPs. We demonstrate the effectiveness of our approaches via numerical experiments by applying our proposed approximations to randomly generated instances and two application problems: the joint decision and estimation problem and the two-trust-region subproblem. The numerical results show significant advantages of our approaches in terms of solution quality and computational time compared with existing benchmark approaches. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods and Analysis. Funding: K. Pan was supported in part by the Research Grants Council of Hong Kong [Grant 15503723]. J. Cheng and B. Yang were supported in part by the Office of Naval Research [Grant N00014-20-1-2154]. J. Cheng was supported in part by the National Science Foundation [Grant ECCS-2404412]. B. Yang was supported in part by the Air Force Office of Scientific Research [Grant FA9550-23-1-0508]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0719 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0719 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

Abstract The work described is motivated by an inability to extend central infrastructure for power and water to low-population-density areas of the Navajo Nation and elsewhere. It is estimated that 35% of the Navajo population haul water for household use, frequently from unregulated sources of poor initial quality. The proposed household-scale, solar-driven nanofiltration (NF) system designs are economically optimized to satisfy point-of-use water purification objectives. The systems also provide electrical energy for a degree of nighttime household illumination. Results support rational design of multiple-component purification systems consisting of solar panels, a high-pressure pump, NF membranes, battery storage and an electrical control unit subject to constraints on daily water treatment and excess energy generation. The results presented are conditional (based on initial water quality, membrane characteristics and geography) but can be adapted to satisfy alternative treatment objectives in alternate geographic, etc. settings. The unit costs of water and energy from an optimized system that provides 100 gpd (1 gallon is 3.78 L) and 2 kWh/day of excess electrical energy are estimated at $0.16 per 100 gallons of water treated and $0.26 per kWh of nighttime electrical energy delivered. Methods can be used to inform dispersed infrastructure design subject to alternate constraint sets in similarly remote areas.